<html>
<head>
<link rel="stylesheet" href="../blueprint/screen.css" type="text/css" media="screen, projection">

<title>TopoColour</title>

<link rel="stylesheet" href="../css/styles.css" type="text/css" media="screen,print">

</head>
<body>
<div class="container">

<h1>TopoColour</h1>
<p>
TopoColour uses graph theory to colour polygon layers. Furthermore it can save the adjacency as a
DOT format file and create a layer showing the adjacencies.
</p>

<h1>Instructions</h1>
<ul>
<li>Start topocolour from the plugin menu</li>
<li>Choose a Layer and Attribute</li>
<li>Choose a 'colouring' algorithm and apply it</li>
<li>Choose a colour palette and style and apply it</li>
</ul>

<h2>Start</h2>
<p>
QGis plugins must be installed and then activated from the plugin menu. TopoColour adds
one option to an entry in the Plugins menu. Start by running it from there.
</p>
<p>
You'll need a polygon layer to work on. Here I'll show you how to colour the countries of Africa 
so that no two adjacent polygons are in the same colour. I load my Africa shapefile and it looks like this:
</p>
<img src="screengrabs/step0.png">

<h2>Choose Layer</h2>
<p>
When I start the plugin it asks me for a layer and attribute. I use the CNTRY_NAME attribute which is
unique for countries.
</p>
<img src="screengrabs/step1.png">

<h2>Choose Colouring</h2>
<p>
Once I've selected the attribute the plugin computes the adjacency between polygons in the layer. This may 
take some time, so a progress dialog allows you to cancel it. Beware that large layers may be very slow at 
this point, or even crash QGis if memory becomes a problem.
<p>
When the adjacency is computed, the main tabbed dialog appears. The first tab is the Graph Colouring tab.
</p>
<img src="screengrabs/step2.png">
<p>
Graph colouring, or vertex colouring, is an operation in graph theory. In our case the graph nodes are
countries and the graph edges represent adjacencies between countries. Our colouring algorithm assigns
numbers to the nodes so that no two directly connected nodes have the same number.
</p>
<p>
The plugin may eventually have a selection of colouring algorithms. Choose one from the dropdown box and 
click 'Compute Colouring'. This will then work out how many colours are needed for the graph and display this 
on the dialog. If the algorithm has randomness in it, you could try computing it again to get a different number
of colours. For example, the current Greedy algorithm chooses which node to work on randomly. In the
text below the algorithm buttons you'll see a list of the adjacencies in the map.
</p>
<p>When you are happy with the graph colouring you can move on to the Layer Style tab</p>

<h2>Layer Styling</h2>
<img src="screengrabs/step3.png">
<p>
This dialog lets you choose a colour scheme and style for the layer. The colour palettes are derived from 
<a href="http://www.colorbrewer.org">Color Brewer</a> qualitative palettes. You can also choose the line width, style, and colour. When happy with your choice, hit 'Apply'.
</p>

<h2>Finished Product</h2>
<img src="screengrabs/step4.png">
<p>
Now you can see the result - a map of Africa with no adjacent countries the same colour.
</p>


<h2>Other Features and Notes</h2>
<h3>Adjacency Layer</h3>
<p>If you click the "Add Adjacency Layer" button then a new layer will appear on your map. This shows which features
are adjacent to which other features. Note that the point used for a feature is the centre of the bounding box, so there's 
no guarantee that it will lie within the feature's polygons. Each line has an attribute giving the attribute values of 
the nodes it connects. Here's what the African adjacency layer looks like:
<img src="screengrabs/step5.png">
The layer is kept in memory, so save it as a shapefile to preserve it.
</p>
<h3>Save DOT file</h3>
<p>This button lets you save the adjacency as a DOT format file. This is not a map or GIS format, and only
stores the connections between polygons. DOT files can be visualised and mapped in various ways. Check out <a href="http://www.graphviz.org/">GraphView</a> for more information.
</p>

<h3>Algorithm Details</h3>
<h4>Greedy</h4>
<p>
This operates as follows:
<pre>
start with all nodes uncoloured
repeat:
  pick an uncoloured node at random
  colour this node with the smallest integer
       not contained in the set of adjacent node colours
  for all nodes
</pre>
This algorithm has randomness, so repeated application may result in different numbers of colours needed.
</p>

<h3>Planar Graphs and The Four-Colour Theorem</h3>

<p>In theory, all polygon maps without overlaps or exclaves should be colourable
with 4 colours or fewer. This is the famous (infamous?) Four-Colour
Theorem. In practice GIS data sets will probably need more, and anyway an algorithm to
find a four-colouring could be complex. Given that a GIS data set might not even be planar because
of features being non-contiguous (e.g. having islands).
</p>

<h2>Credits</h2>
<p>
Written by Barry Rowlingson &lt;b.rowlingson@lancaster.ac.uk&gt;
</p>


</div>
</body>
</html>
